作業系統L6－同步

臨界區間(critical section)

每一行程中的部分程式碼，可以共同改變變數，更新表格，寫入檔案

區間結構

• 入口區段(entry section):臨界區間入口
• 出口區段(exit section):臨界區間出口
• 剩餘區段(remainder section)
  

臨界區間問題

條件

• 互斥(Mutual Exclusion):若有行程已在臨界區間執行，其他行程不能再同區間執行
• 進行(Progress):被選擇的行程不得被無限延遲下去
• 限制性等待(Bounded Waiting):一個行程被要求進入臨界區間答應前，允許其他一個行程進入

問題解答

• 可搶先核心(preemptive kernels):核心模式執行時可搶先
• 不可搶先核心(nonpreemptive kernels):離開核心模式或自動交出CPU時才可搶先

同步硬體

鎖(locking)

• 用於保護臨界區間
• 單一處理器可停止中斷，多處理器較沒效率

同步軟體

互斥鎖(Mutex Lock)

• acquire():取得鎖
• release():釋放鎖
• 忙碌等待(busy waiting)
• 自旋鎖(spinlock)

號誌(Semaphore)

• 不需要忙碌等待的同步工具
• 計數號誌(Counting semaphore):不受限制的整數值
• 二元號誌(Binary semaphore):數值可以是0,1，可用來取代互斥鎖

無忙碌等待的號誌

• 每個號誌都有一個相關聯的等待佇列
• 數值(整數型態)
• 指向串列的下一筆紀錄
• 操作
  • block:把呼叫操作的行程放到適當的等候佇列
  • wakeup:移除等候佇列的一個行程，放到就緒佇列

死結和飢餓

• 死結(Dead Lock):兩個以上的行程等待一個只能被等待的行程
• 飢餓(Starvation):無限期阻隔
• 優先權倒置(Priority Inversion):高優先權行程被低優先權行程鎖把持造成排班問題，需用**優先權繼承協定(priority-inheritance protocol)**解決

典型的同步問題

有限緩衝區問題

• n個緩衝區,每一個緩衝區保存一項資料

讀取者-寫入者問題

• 讀取者:只能讀取資料集;它們不能執行資料集
• 寫入者:可以讀和寫資料集
• 允許許多讀取者同時去讀取共用資料
• 同一時間只有一個寫入者可以存取資料

讀取者-寫入者問題的變形

• 除非有寫入者已獲得允許去使用共用資料，否則讀取者不需保持等候狀態
• 只要寫入者準備好之後，需要盡快的撰寫共用資料

哲學家進餐的問題(Dining-philosophers Problem)

• 需兩枝筷子才能吃，吃完同時放下兩枝筷子
  

監督程式

• 一種對於行程同步提供方便和有效機制的高階使用一組操作資料的函數來封裝資料
• 抽象資料型態(abstract data type,ADT):只能由程序內執行碼存取的內部變數

條件變數

condition x, y;

• x.wait () :使用後的行程會被暫停，直到x.signal ()發生
• x.signal ():恢復因為x.wait ()而被暫停的行程